#include <iostream>
#include <cstdlib>


template <typename T>
class BinaryTree
{
private:
    class Node
    {
    public:
	T data;
	Node* lc;
	Node* rc;
	Node* parent;
	Node(T _data);
    };
    Node* root;
    void inorder_walk(Node* _x) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    Node* predecessor(Node* _x) const;
public:
    BinaryTree() {root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    Node* get_root() const;
    void inorder_walk() const;
    int tree_search(T _data, Node* _x) const;
    void test_successor();
};

template <typename T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template <typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template <typename T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
    
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
	return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->lc != NULL)
	return max(x->lc);
    Node* y = x->parent;
    while (y != NULL && x == y->lc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};


template <typename T>
void BinaryTree<T>::test_successor()
{
    std::cout << "successor: " << successor(root->lc->lc->rc)->data << std::endl;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
    while (_x->rc != NULL)
	_x = _x->rc;
    return _x;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::get_root() const
{
  return root;
};

template <typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template <typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "\t";
	inorder_walk(_x->rc);
    }
};

template <typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    while (x != NULL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    p->parent = y;
    if (y == NULL)
	root = p;
    else if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
};

template <typename T>
int BinaryTree<T>::tree_search(T _data, Node* _x) const
{
   int flag = 1;
   Node* x = _x;
   if (x != NULL)
    {
      tree_search(_data, x->lc);
	if (x->data == _data)
	  {
	    if(x == root)
	      {
		std::cout << "Found!" << std::endl;
		flag = 0;
		return 0;
	      }
	    else
	      {
		flag = 0;
		return 0;
	      }
	  }
        tree_search(_data, x->rc);
	if (flag == 1)
	  {
	    if(x == root)
	      {
		std::cout << "Not Found!" << std::endl;
		return 0;
	      }
	    else
	      {
		return 0;
	      }
	  }
    }
   else
     {
       	if(x == root)
	      {
		std::cout << "Empty BST" << std::endl;
		return 0;
	      }
        else
	      {
		return 0;
	      }	
     }
};

template <typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
	root = p;
};

template <typename T>
void BST_sort(T* _head, int _length)
{
  BinaryTree<T> tree;
  for (int i = 0; i < _length; i++)
    {
      tree.insert(*(_head + i));
    }
  tree.inorder_walk();
};

